// 二叉搜索树的最近公共祖先

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class Solution_235_1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> ancestor1 = new ArrayList<>();
        List<TreeNode> ancestor2 = new ArrayList<>();
        Ancestor(root, p, ancestor1);
        Ancestor(root, q, ancestor2);
        // ancestor1.forEach(node -> System.out.println(node.val));
        // ancestor2.forEach(node -> System.out.println(node.val));
        if (ancestor1.contains(q))
            return q;
        if (ancestor2.contains(p))
            return p;
        // for (int i = ancestor1.size() - 1; i >= 0; i--) {
        // for (int j = ancestor2.size() - 1; j >= 0; j--) {
        // if (ancestor1.get(i).val == ancestor2.get(j).val)
        // return ancestor1.get(i);
        // }
        // }
        // 寻找最后一个相同的结点
        TreeNode result = ancestor1.get(0);
        for (int i = 0; i < Math.min(ancestor1.size(), ancestor2.size()); i++) {
            if (ancestor1.get(i) == ancestor2.get(i))
                result = ancestor1.get(i);
        }
        return result;
    }

    public void Ancestor(TreeNode root, TreeNode node, List<TreeNode> list) {
        while (root.val != node.val) {
            list.add(root);
            if (root.val < node.val)
                root = root.right;
            else if (root.val > node.val)
                root = root.left;
        }
    }
}

class Solution_235_2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}